#ifndef __CACHE_H__
#define __CACHE_H__

#include <map>
#include <list>
using namespace std;

/* The Key and Value in a cache will almost always 
   be of different types :)
*/
template<typename K, typename V>
class Cache
{
private:
  list<K> lru_keys;
  map<K,V> cache;
  /* update_list:
     called internally by lookup, where in the list ltu_keys will 
     be updated accoringly so that most recently accessed key is
     at the tail of the list and the least recently use is at the
     head of the list. We cannot use a STL queue, because, a key
     in any index of the list might be removed and added to the 
     end when accessed.
  */
  void update_list(K);
  void add_to_cache(K,V);
  void remove_from_cache(K);


public:
  Cache();
  /* In case we are supporting multiple types of caches later, we
     can create a cache object by passing as parameter the type of
     cache, which can be a public static const int.
  */
  Cache(int);
  ~Cache();
  void add_to_cache(K,V);
  /* Will return NULL on failure ? */
  V lookup(K);
};
#endif
